Implementing a Singly Linked List in Python

Posted on







链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。



链表节点类的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Node:
    def __init__(self,initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

生成一个节点对象：

1
2
3
>>> temp = Node(93)
>>> temp.getData()
93

结构如下图所示：



链表类的实现

1
2
3
4
class UnorderedList:

    def __init__(self):
        self.head = None

新建一个链表对象：

1
>>> mylist = UnorderedList()

往链表前端中加入节点

1
2
3
4
def add(self,item):
    temp = Node(item)
    temp.setNext(self.head)
    self.head = temp
1
2
3
4
5
6
>>> mylist.add(31)
>>> mylist.add(77)
>>> mylist.add(17)
>>> mylist.add(93)
>>> mylist.add(26)
>>> mylist.add(54)

现在链表结构如下图所示：



在链表尾端添加节点

1
2
3
4
5
6
7
8
9
def append(self,item):
    temp=Node(item)
    if self.head == None:
        self.head=item
    else:
        current=self.head
        while current.getNext()!=None:
            current=current.getNext
        current.setNext(temp)

链表的长度计算

1
2
3
4
5
6
def size(self):
    count=0
    current=self.head
    while current.getNext !=None:
        count=count+1
        current=current.getNext

计算过程如下图所示：



寻找是否存在某一节点

1
2
3
4
5
6
7
8
9
def serch(self,item):
    current=self.head
    while current.getNext()!=None:
        if current.getData==item:
            return True
        else:
            current=current.getNext()

    return False

删除某一节点

1
2
3
4
5
6
7
8
9
10
11
12
13
def remove(self,item):
    current=self.head
    pre=None
    while current!=None:
        if current.getData()==item:
            if not pre:
                self.head=current.getNext()
            else:
                pre.setNext(current.getNext())
            break
        else:
            pre=current
            current=current.getNext()

链表反转

1
2
3
4
5
6
7
8
9
def rev(self):
    pre=None
    current=self.head
    while current!=None:
        next=current.getNext()
        current.setNext=pre
        pre=current
        curren=next
    return pre

链表成对调换

例如：1->2->3->4转换成2->1->4->3

1
2
3
4
5
6
7
def pairswap(self):
    curren=self.head
    while curren!=None and curren.getNext().getNext()!=None:
        temp=curren.getData()
        curren.setData(curren.getNext().getData())
        curren.getNext().setData(temp)
        curren=curren.getNext().getNext()